package com.yuan.algorithms.arithmetic_1;

/*
time:2014/11/20
 完成时间：20150328
 explain:素数环http://acm.hdu.edu.cn/showproblem.php?pid=1016
 给定数n(n<20)，在n的所有排列中，记a[1],a]2],...,a[n]，
 求满足a[i]+a[i+1](1<=i<n)是素数并且a[1]+a[n]也是素数的所有排列。排列按字典序输出。
 Sample Input
 6
 8

 Sample Output
 Case 1:
 1 4 3 2 5 6
 1 6 5 2 3 4

 Case 2:
 1 2 3 8 5 6 7 4
 1 2 5 8 3 4 7 6
 1 4 7 6 5 8 3 2
 1 6 7 4 3 8 5 2
 */
import java.util.Scanner;

public class 递归_素数环 {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = 0;
		while (sc.hasNext()) {
			int n = sc.nextInt();
			num++;
			int[] arr = new int[n];
			arr[0] = 1;
			boolean[] mark = new boolean[n + 1];
			System.out.println("Case " + num + ":");
			f(n, arr, mark, 1);
			System.out.println();
		}
	}

	/**
	 * 
	 * @param n
	 *            数列长度
	 * @param arr
	 *            素数环缓存数组
	 * @param mark
	 *            标记数组
	 * @param current
	 *            当前位置
	 */
	private static void f(int n, int[] arr, boolean[] mark, int current) {
		if (current >= n) {
			for (int i = 0; i < arr.length; i++) {
				if (i == arr.length - 1) {
					System.out.println(arr[i]);
				} else {
					System.out.print(arr[i] + " ");
				}
			}
			return;
		}
		for (int i = 2; i <= n; i++) {
			if (mark[i]) {// 如果这个数已经使用过了，则跳过
				continue;
			}
			// 递归填数
			if (current == n - 1) {// 最后一位填的数和其前一位以及第一位数相加必须是素数
				if (isPrime(i + arr[0]) && isPrime(i + arr[current - 1])) {
					arr[current] = i;
					mark[i] = true;
					f(n, arr, mark, current + 1);
					mark[i] = false;
				}
			} else {// 填的数和其前面的数相加必须是素数
				if (isPrime(i + arr[current - 1])) {
					arr[current] = i;
					mark[i] = true;
					f(n, arr, mark, current + 1);
					mark[i] = false;
				}
			}
		}
	}

	/**
	 * 素数判断
	 * @param n
	 * @return 是否是素数
	 */
	public static boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}
		if (n % 2 == 0 && n != 2) {
			return false;
		}
		for (int i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}
